package com.shm.leetcode;

import java.util.*;

/**
 * @author: shm
 * @dateTime: 2020/11/22 10:24
 * @description: 242. 有效的字母异位词
 * 给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的字母异位词。
 *
 * 示例 1:
 *
 * 输入: s = "anagram", t = "nagaram"
 * 输出: true
 * 示例 2:
 *
 * 输入: s = "rat", t = "car"
 * 输出: false
 * 说明:
 * 你可以假设字符串只包含小写字母。
 *
 * 进阶:
 * 如果输入字符串包含 unicode 字符怎么办？你能否调整你的解法来应对这种情况？
 */
public class IsAnagram {
    public boolean isAnagram(String s, String t) {
        if (s.length()!=t.length()){
            return false;
        }
        HashMap<Character,Integer> map = new HashMap<>();
        for(int i=0;i<s.length();i++){
            map.put(s.charAt(i),map.getOrDefault(s.charAt(i),0)+1);
        }
        for(int j=0;j<t.length();j++){
            if(!map.containsKey(t.charAt(j))){
                return false;
            }else{
                map.put(t.charAt(j),map.get(t.charAt(j))-1);
            }
        }

//        Set<Map.Entry<Character, Integer>> entries = map.entrySet();
//        for (Map.Entry<Character, Integer> entry : entries) {
//            if (entry.getValue()!=0){
//                return false;
//            }
//        }

        Set<Character> set =  map.keySet();
        for(Character c:set){
            if(map.get(c)!=0){
                return false;
            }
        }



//        for (int i = 0; i < t.length(); i++) {
//            char ch = t.charAt(i);
//            map.put(ch, map.getOrDefault(ch, 0) - 1);
//            if (map.get(ch) < 0) {
//                return false;
//            }
//        }
//        return true;

//        作者：LeetCode-Solution
//        链接：https://leetcode-cn.com/problems/valid-anagram/solution/you-xiao-de-zi-mu-yi-wei-ci-by-leetcode-solution/
        return true;
    }

    /***
     * 方法二：哈希表
     * 从另一个角度考虑，tt 是 ss 的异位词等价于「两个字符串中字符出现的种类和次数均相等」。
     * 由于字符串只包含 2626 个小写字母，因此我们可以维护一个长度为 2626 的频次数组 \textit{table}table，
     * 先遍历记录字符串 ss 中字符出现的频次，然后遍历字符串 tt，减去 \textit{table}table 中对应的频次，
     * 如果出现 \textit{table}[i]<0table[i]<0，则说明 tt 包含一个不在 ss 中的额外字符，返回 \text{false}false 即可。
     * 复杂度分析
     *
     * 时间复杂度：O(n)O(n)，其中 nn 为 ss 的长度。
     *
     * 空间复杂度：O(S)O(S)，其中 SS 为字符集大小，此处 S=26S=26。
     *
     * 作者：LeetCode-Solution
     * 链接：https://leetcode-cn.com/problems/valid-anagram/solution/you-xiao-de-zi-mu-yi-wei-ci-by-leetcode-solution/
     * @param s
     * @param t
     * @return
     */
    public boolean isAnagram_2(String s, String t) {
        if (s.length() != t.length()) {
            return false;
        }
        int[] table = new int[26];
        for (int i = 0; i < s.length(); i++) {
            table[s.charAt(i)-'a']++;
        }
        for (int i = 0; i < t.length(); i++) {
            table[t.charAt(i)-'a']--;
            if (table[t.charAt(i)-'a']<0){
                return false;
            }
        }
        return true;
    }

    /***
     * 方法一：排序
     * tt 是 ss 的异位词等价于「两个字符串排序后相等」。因此我们可以对字符串 ss 和 tt 分别排序，看排序后的字符串是否相等即可判断。
     * 此外，如果 ss 和 tt 的长度不同，tt 必然不是 ss 的异位词。
     *
     * 复杂度分析
     *
     * 时间复杂度：O(n \log n)O(nlogn)，其中 nn 为 ss 的长度。排序的时间复杂度为 O(n\log n)O(nlogn)，比较两个字符串是否相等时间复杂度为 O(n)O(n)，因此总体时间复杂度为 O(n \log n+n)=O(n\log n)O(nlogn+n)=O(nlogn)。
     *
     * 空间复杂度：O(\log n)O(logn)。排序需要 O(\log n)O(logn) 的空间复杂度。注意，在某些语言（比如 Java & JavaScript）中字符串是不可变的，因此我们需要额外的 O(n)O(n) 的空间来拷贝字符串。但是我们忽略这一复杂度分析，因为：
     *
     * 这依赖于语言的细节；
     * 这取决于函数的设计方式，例如，可以将函数参数类型更改为 char[]。
     *
     * 作者：LeetCode-Solution
     * 链接：https://leetcode-cn.com/problems/valid-anagram/solution/you-xiao-de-zi-mu-yi-wei-ci-by-leetcode-solution/
     * @param s
     * @param t
     * @return
     */
    public boolean isAnagram_3(String s, String t) {
        if (s.length() != t.length()) {
            return false;
        }
        char[] chars = s.toCharArray();
        char[] chart = t.toCharArray();
        Arrays.sort(chars);
        Arrays.sort(chart);
//        return Arrays.toString(chars).equals(Arrays.toString(chart));
        return Arrays.equals(chars,chart);
    }
}
